0858. 镜面反射【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 数学

1. 📝 题目描述

• leetcode

有一个特殊的正方形房间，每面墙上都有一面镜子。除西南角以外，每个角落都放有一个接受器，编号为 0， 1，以及 2。

正方形房间的墙壁长度为 p，一束激光从西南角射出，首先会与东墙相遇，入射点到接收器 0 的距离为 q。

返回光线最先遇到的接收器的编号（保证光线最终会遇到一个接收器）。

---

示例 1：

输入：p = 2, q = 1
输出：2
解释：这条光线在第一次被反射回左边的墙时就遇到了接收器 2。

示例 2：

输入：p = 3, q = 1
输入：1

---

提示：

• 1 <= q <= p <= 1000

2. 🎯 s.1 - 数学

c

int mirrorReflection(int p, int q) {
    while (p % 2 == 0 && q % 2 == 0) { p /= 2; q /= 2; }
    if (p % 2 == 0) return 2;
    if (q % 2 == 0) return 0;
    return 1;
}

js

/**
 * @param {number} p
 * @param {number} q
 * @return {number}
 */
var mirrorReflection = function (p, q) {
  while (p % 2 === 0 && q % 2 === 0) {
    p /= 2
    q /= 2
  }
  if (p % 2 === 0) return 2
  if (q % 2 === 0) return 0
  return 1
}

py

class Solution:
    def mirrorReflection(self, p: int, q: int) -> int:
        while p % 2 == 0 and q % 2 == 0:
            p //= 2
            q //= 2
        if p % 2 == 0: return 2
        if q % 2 == 0: return 0
        return 1

• 时间复杂度：$O(\log p)$
• 空间复杂度：$O(1)$

算法思路：

• 将 p 和 q 同时除以 2 直到至少一个为奇数
• p 偶 q 奇返回 2，p 奇 q 偶返回 0，均奇返回 1